package msb.class08;

import java.util.HashMap;

/**
 * 前缀树
 */
public class Code01_TrieTree {

    /**
     * 前缀树节点
     */
    public static class Node {
        public int pass;
        public int end;
        public HashMap<Integer, Node> nexts = new HashMap<>();
    }

    public static class TrieTree {

        /**
         * 根据点
         */
        public Node root;

        public TrieTree() {
            root = new Node();
        }

        public void insert(String str) {
            if (str == null || str.length() == 0) {
                return;
            }
            Node node = root;
            node.pass++;
            char[] charArray = str.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                if (!node.nexts.containsKey((int) charArray[i])) {
                    Node cur = new Node();
                    node.nexts.put((int) charArray[i], cur);
                }
                node = node.nexts.get((int) charArray[i]);
                node.pass++;
            }
            node.end++;
        }

//        public void insert(String word) {
//            if (word == null) {
//                return;
//            }
//            char[] chs = word.toCharArray();
//            Node node = root;
//            node.pass++;
//            int index = 0;
//            for (int i = 0; i < chs.length; i++) {
//                index = (int) chs[i];
//                if (!node.nexts.containsKey(index)) {
//                    node.nexts.put(index, new Node());
//                }
//                node = node.nexts.get(index);
//                node.pass++;
//            }
//            node.end++;
//        }

        public void delete(String str) {
            if (str == null || str.length() == 0) {
                return;
            }
            if (search(str) > 0) {
                Node node = root;
                node.pass--;
                char[] charArray = str.toCharArray();
                for (int i = 0; i < charArray.length; i++) {
                    node = node.nexts.get((int) charArray[i]);
                    node.pass--;
                }
                node.end--;
            }
        }

        public int search(String str) {
            if (str == null || str.length() == 0) {
                return 0;
            }
            Node node = root;
            char[] charArray = str.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                if (node.nexts.containsKey((int) charArray[i])) {
                    node = node.nexts.get((int) charArray[i]);
                } else {
                    return 0;
                }
            }
            return node.end;
        }

        public int prefix(String str) {
            if (str == null || str.length() == 0) {
                return 0;
            }
            Node node = root;
            char[] charArray = str.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                if (node.nexts.containsKey((int) charArray[i])) {
                    node = node.nexts.get((int) charArray[i]);
                } else {
                    return 0;
                }
            }
            return node.pass;
        }
    }

    public static class Right {

        private HashMap<String, Integer> box;

        public Right() {
            box = new HashMap<>();
        }

        public void insert(String word) {
            if (!box.containsKey(word)) {
                box.put(word, 1);
            } else {
                box.put(word, box.get(word) + 1);
            }
        }

        public void delete(String word) {
            if (box.containsKey(word)) {
                if (box.get(word) == 1) {
                    box.remove(word);
                } else {
                    box.put(word, box.get(word) - 1);
                }
            }
        }

        public int search(String word) {
            if (!box.containsKey(word)) {
                return 0;
            } else {
                return box.get(word);
            }
        }

        public int prefixNumber(String pre) {
            int count = 0;
            for (String cur : box.keySet()) {
                if (cur.startsWith(pre)) {
                    count += box.get(cur);
                }
            }
            return count;
        }
    }

    // for test
    public static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 6);
            ans[i] = (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    // for test
    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    public static void main(String[] args) {
        int arrLen = 100;
        int strLen = 20;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            TrieTree trie1 = new TrieTree();
            Right right = new Right();
            for (int j = 0; j < arr.length; j++) {
                double decide = Math.random();
                if (decide < 0.25) {
                    trie1.insert(arr[j]);
                    right.insert(arr[j]);
                } else if (decide < 0.5) {
                    trie1.delete(arr[j]);
                    right.delete(arr[j]);
                } else if (decide < 0.75) {
                    int ans1 = trie1.search(arr[j]);
                    int ans3 = right.search(arr[j]);
                    if (ans1 != ans3) {
                        System.out.println("search!");
                    }
                } else {
                    int ans1 = trie1.prefix(arr[j]);
                    int ans3 = right.prefixNumber(arr[j]);
                    if (ans1 != ans3) {
                        System.out.println("ans1=" + ans1 + ",ans3=" + ans3);
                        System.out.println("prefix!");
                    }
                }
            }
        }
        System.out.println("finish!");

    }
}
